#include "listnode.h"
// https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
int getLengh(struct ListNode* head)
{
    int length = 0;
    struct ListNode* h = head;
    while (h)
    {
        h = h->next;
        length++;
    }
    return length;
}

struct ListNode* removeNthFromEnd1(struct ListNode* head, int n)
{

    struct ListNode* dummy = malloc(sizeof(struct ListNode));
    dummy->val = 0;
    dummy->next = head;

    struct ListNode* d = dummy;
    int len = getLengh(head);
    for (int i = 0; i < len - n; i++)
    {
        d = d->next;
    }
    struct ListNode* willFree = d->next;
    d->next = d->next->next;
    free(willFree);
    return dummy->next;
}

struct ListNode* removeNthFromEnd(struct ListNode* head, int n)
{
    if (!head)
    {
        return NULL;
    }

    struct ListNode* dummy = malloc(sizeof(struct ListNode));
    dummy->val = 0;
    dummy->next = head;
    struct ListNode* slow = dummy;
    struct ListNode* fast = head;
    while (n--)
    {
        fast = fast->next;
    }
    while (fast)
    {
        slow = slow->next;
        fast = fast->next;
    }

    struct ListNode* willFree = slow->next;
    slow->next = slow->next->next;
    free(willFree);
    struct ListNode* ans = dummy->next;
    free(dummy);
    return ans;
}

struct ListNode* removeNthFromEnd(struct ListNode* head, int n)
{
    if (!head)
    {
        return NULL;
    }

    struct ListNode* slow = head;
    struct ListNode* fast = head;
    struct ListNode* prev = NULL;

    // 让 fast 先移动 n 步
    while (n--)
    {
        fast = fast->next;
    }

    // 如果 fast 到达链表末尾，说明要删除的节点是头节点
    if (!fast)
    {
        struct ListNode* temp = head;
        head = head->next;
        free(temp);
        return head;
    }

    // 同时移动 slow 和 fast，直到 fast 到达链表末尾
    while (fast)
    {
        prev = slow;
        slow = slow->next;
        fast = fast->next;
    }

    // 删除 slow 指向的节点
    prev->next = slow->next;
    free(slow);

    return head;
}
